package set.src;

import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;

/**
 * 
 * @author Erik Sapir & Lior Zibi
 * 
 * Optimistic Global List implementation: search that element exist 
 * and than lock using global lock
 * 
 * @param T Item type.
 */
public class OptimisticGlobalList<T> implements Set<T> {
	/**
	 * First list node
	 */
	private volatile Node m_head;
	
	/**
	 * number of element in the list
	 */
	private volatile int m_size;
	 
	/**
	 * Synchronizes access to list
	 */
	private Lock m_lock;
   
	/**
	 * Constructor
	 */
	public OptimisticGlobalList(int numOfThreads) {
		System.out.println("\n\tSet Is: Optimistic Global List\n");
		
		// Add sentinels to start and end
		this.m_head  = new Node(Integer.MIN_VALUE);
		this.m_head.m_next = new Node(Integer.MAX_VALUE);
		
		this.m_lock = new ReentrantLock();
		this.m_size = 0;
	}
	
	public boolean add(T item, int threadID) {
		int key = item.hashCode();
    
		while (true) {
			Node pred = this.m_head;
			Node curr = pred.m_next;
			
			//search for first element equal or larger than new element
			while (curr.m_key <= key) {
				pred = curr; curr = curr.m_next;
			}
			
			//once found - lock the list
			m_lock.lock();
			
			try {
				//make sure pred and curr still exist and list and that pred.next = curr 
				if (validate(pred, curr)) {
					if (curr.m_key == key) {
						// element already exist in list - nothing to add
						return false;
					} else {               
						// add element to list
						Node node = new Node(item);
						node.m_next = curr;
						pred.m_next = node;
                    
						//element added successfully - increment number of elements in list
						m_size++;
						
						return true;
					}
				}
			} finally {                
				m_lock.unlock(); // always unlock
			}
		}
	}
  
	public boolean remove(T item, int threadID) {
		int key = item.hashCode();
		
		while (true) {
			Node pred = this.m_head;
			Node curr = pred.m_next;
			
			//search for first element equal or larger than element to be removed
			while (curr.m_key < key) {
				pred = curr; curr = curr.m_next;
			}
			
			//lock the list
			m_lock.lock();
			
			try {
				//make sure pred and curr still exist and list and that pred.next = curr 
				if (validate(pred, curr)) {
					if (curr.m_key == key) { 
						// remove element from list
						pred.m_next = curr.m_next;
        
						//element removed successfully - decrement number of elements in list
						m_size--;
						
						return true;
					} else {               
						// element was not found in list - nothing to remove
						return false;
					}
				}
			} finally {
				m_lock.unlock(); // always unlock
			}
		}
	}
 
	public boolean contains(T item, int threadID) {
		int key = item.hashCode();
		
		while (true) {
			Node pred = this.m_head; // sentinel node;
			Node curr = pred.m_next;
  
			//search for first element equal or larger than element we are searching
			while (curr.m_key < key) {
				pred = curr; curr = curr.m_next;
			}
  
			//lock the list
			m_lock.lock();
			
			try {
				//make sure pred and curr still exist and list and that pred.next = curr 
				if (validate(pred, curr)) {
					//return true iff element is in the list
					return (curr.m_key == key);
				}
			} finally {                
				m_lock.unlock(); // always unlock
			}
		}
	}
	  
	public void clean(int threadID) {

		//lock the list
		m_lock.lock();
	
		try {
			//create new tail and set head.next = tail.
			//in that way all other elements are removed because
			//they are no longer reachable from head
			m_head.m_next = new Node(Integer.MAX_VALUE);  
			
			//no elements in the list now
			m_size = 0;
		} finally {
			m_lock.unlock(); //always unlock
		}
	}

	public boolean isEmpty(int threadID) {
		return (m_size == 0);
	}

	public int size(int threadID) {
		return m_size;
	}
	
	/**
	 * Check that prev and curr are still in list and adjacent
	 * @param pred predecessor node
	 * @param curr current node
	 * @return whther predecessor and current have changed
	 */
	private boolean validate(Node pred, Node curr) {
		Node node = m_head;
    
		while (node.m_key <= pred.m_key) {
			if (node == pred)
				return pred.m_next == curr;
			node = node.m_next;
		}
    
		return false;
	}
	
	/**
	 * list node
	 */
	private class Node {
		/**
		 * actual item
		 */
		final T m_item;
		
		/**
		 * item's hash code
		 */
		final int m_key;
		
		/**
		 * next node in list
		 */
		volatile Node m_next;

		/**
		 * Constructor for usual node
		 * @param item element in list
		 */
		Node(T item) {
			this.m_item = item;
			this.m_key = item.hashCode();
		}

		/**
		 * Constructor for sentinel node
		 * @param key should be min or max int value
		 */
		Node(int key) {
			this.m_key = key;
			this.m_item = null;
		}

	}
	
}
